The present invention relates to a straight-line detecting method for extracting a straight line lying in an X-Y plane of, e.g., an image.
Recently, there has been developed an automatic travelling vehicle which is capable of taking an image of an area ahead of the vehicle through a video camera attached thereto, detecting edges of a road or divisional lines indicated thereon in the image by applying an image processing technique and recognizing a permissible travelling area on the road.
A line segment existing in a X-Y plane of, e.g., an image is usually detected by such a straight-line detecting method which generates a Hough transformed curve relating to an edge point by utilizing the continuity of edge points on a straight line, gives a vote to a pixel through which the curve passes and, thereby, determines a straight line by detecting a peak point according to the number of votes of pixels in a space defined by the Hough transform parameters.
According to the above-mentioned method, voting is made of all the pixels corresponding to parameters of straight lines that have the possibility to pass through an edge point. This means that a part of the total number of votes is given to line parameters that can not be even candidates. Consequently, the parameter space expands and requires a large number of voting times. This requires a large-capacity memory for voting and takes substantial time for processing data. Neighbors to pixels corresponding to the line parameters may also have votes, causing poor distinctness of a peak point, i.e., decreasing an accuracy of detecting the straight line.
Another combinatorial Hough transform method has been also proposed.
Hough transformation parameters for a straight line passing a remarkable edge point (x1, y1) in an X-Y plane and another edge point (x2, y2) are determined according to the equations: EQU .theta.=a tan{(x1-x2)/(y1-y2)} (1) EQU .rho.=x1 cos .theta.+y1 sin .theta. (2)
A vote is given only to a pixel corresponding to (.theta., .rho.).
The combinatorial Hough transform method improves the accuracy of detecting a straight line since only pixels corresponding to a straight line collects votes, thus obtaining a distinct peak point. This method, however, also requires substantial time to process the data since the number of voting times considerably and sharply increases.
Accordingly, the conventional combinatorial Hough transform method restricts a voting area to two points which satisfies the following conditions concerning two points (x1, y2) and (x2, y2): EQU .vertline.x1-x2.vertline.&lt;.epsilon.x (3) EQU .vertline.y1-y2.vertline.&gt;.epsilon.y (4)
where .epsilon.x and .epsilon.y are constants.
This is disclosed in "An unattended travelling system into which image processing and fuzzy reasoning amalgamates", pp. 407-416, Journal FUJITSU No. 42, vol. 4, issued in September of 1991.
FIG. 3 is ilustrative of the above-metioned conditions. As is apparent from FIG. 3, this method may attain an improved sensitivity in vertical (Y) directions but can not attain a sufficient sensitivity in horizontal (X) directions because increasing the sensitivity in X-directions is accompanied by widening a voting area and elongating data-processing time. Furthermore, reducing a voting area in Y-directions makes it hard to detect short line segments.
The problems involved in the conventional method based on a voting type combinatorial Hough transform are such that restricting a voting area to two points satisfying the conditions (3) and (4) relative to the points (x1, y1) and (x2, y2) may increase the processing speed but have a low sensitivity of detecting a straight line in the horizontal direction. It can not efficiently detect short line segments.